/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/search-a-2d-matrix
   @Language: C++
   @Datetime: 19-07-04 12:35
   */

// Method 1, Time O(m+n) 92ms, Space O(1) 12.8MB
class Solution {
public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
		for(int i=matrix.size()-1, j=0; i>-1 && j<matrix[i].size();){
			if(matrix[i][j]<target) ++j;
			else if(matrix[i][j]>target) --i;
			else return true;
		}
		return false;
	}
};
